LowestCommonAncestorHld.java

/*
 * An algorithm to find the lowest common ancestor (LCA) of two nodes in a tree using heavy light decomposition (HLD).
 * 
 * Time complexity:
 * - Preprocessing: O(V + E)
 * - Query: O(log V)
 */

packagecodebook.graph;

importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;
importjava.io.OutputStreamWriter;
importjava.io.PrintWriter;
importjava.util.ArrayList;
importjava.util.StringTokenizer;

publicclassLowestCommonAncestorHld {

staticBufferedReaderbr;
staticPrintWriterout;
staticStringTokenizerst;

staticArrayList<ArrayList<Integer>> adj = newArrayList<ArrayList<Integer>>();
staticint[] depth, parent, chain, size, head;
staticintn, q, chainNum;

publicstaticvoidmain (String[] args) throwsIOException {
br = newBufferedReader(newInputStreamReader(System.in));
out = newPrintWriter(newOutputStreamWriter(System.out));
//br = new BufferedReader(new FileReader("in.txt"));
//out = new PrintWriter(new FileWriter("out.txt"));

// number of nodes
n = readInt();
// number of queries
q = readInt();

depth = newint[n];
parent = newint[n];
chain = newint[n];
size = newint[n];
head = newint[n];

for (inti = 0; i < n; i++) {
adj.add(newArrayList<Integer>());
head[i] = -1;
 }

for (inti = 0; i < n - 1; i++) {
inta = readInt() - 1;
intb = readInt() - 1;
adj.get(a).add(b);
adj.get(b).add(a);
 }

dfs(0, 0, -1);
getHld(0, -1);

for (inti = 0; i < q; i++)
out.println(getLca(readInt() - 1, readInt() - 1) + 1);

out.close();
 }

staticintgetLca (inti, intj) {
while (chain[i] != chain[j]) {
if (depth[head[chain[i]]] < depth[head[chain[j]]])
j = parent[head[chain[j]]];
else
i = parent[head[chain[i]]];
 }
if (depth[i] < depth[j])
returni;
returnj;
 }

staticvoidgetHld (inti, intprev) {
if (head[chainNum] == -1) {
head[chainNum] = i;
 }
chain[i] = chainNum;
intmaxIndex = -1;
for (intj : adj.get(i))
if (j != prev && (maxIndex == -1 || size[maxIndex] < size[j]))
maxIndex = j;
if (maxIndex != -1)
getHld(maxIndex, i);
for (intj : adj.get(i))
if (j != prev && j != maxIndex) {
chainNum++;
getHld(j, i);
 }

 }

staticvoiddfs (inti, intd, intprev) {
depth[i] = d;
parent[i] = prev;
size[i] = 1;
for (intj : adj.get(i)) {
if (j != prev) {
dfs(j, d + 1, i);
size[i] += size[j];
 }
 }
 }

staticStringnext () throwsIOException {
while (st == null || !st.hasMoreTokens())
st = newStringTokenizer(br.readLine().trim());
returnst.nextToken();
 }

staticlongreadLong () throwsIOException {
returnLong.parseLong(next());
 }

staticintreadInt () throwsIOException {
returnInteger.parseInt(next());
 }

staticdoublereadDouble () throwsIOException {
returnDouble.parseDouble(next());
 }

staticcharreadCharacter () throwsIOException {
returnnext().charAt(0);
 }

staticStringreadLine () throwsIOException {
returnbr.readLine().trim();
 }
}